'''
@Company: TWL
@Author: xue jian
@Email: xuejian@kanzhun.com
@Date: 2020-07-18 11:58:00
'''
'''
97. 交错字符串
给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。

示例 1:

输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出: true
示例 2:

输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
输出: false

tips:典型dp,dp[i][j][k]状态表示s1[i-1],s2[j-1],s3[k-1]时，是否满足条件。初始条件dp都是false，边界是dp[0][0][0]为true。转移方程直接看程序，比较简单。
'''

from typing import List
class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        if len(s3) != len(s1)+len(s2):
            return False
        dp = [[[False]*(len(s3)+1) for _ in s2+' '] for _ in s1+' ']
        dp[0][0][0] = True
        for i in range(len(s1)+1):
            for j in range(len(s2)+1):
                if not i and not j:
                    # print(i, j)
                    continue
                k = i+j
                if i > 0:
                    dp[i][j][k] = dp[i][j][k] or (dp[i-1][j][k-1] and s3[k-1] == s1[i-1])
                    # if i == 1 and k==1:
                        # print('should be true:',dp[i][j][k])
                if j>0:
                    dp[i][j][k] = dp[i][j][k] or (dp[i][j-1][k-1] and s3[k-1] == s2[j-1])
        # print(dp[3][1][4])
        return dp[-1][-1][-1]
if __name__ == "__main__":
    s1 = "aabcc"
    s2 = "dbbca"
    s3 = "aadbbcbcac"
    solution = Solution()
    print(solution.isInterleave(s1, s2, s3))